﻿namespace Nomo.PathFindingModule
{
    /// <summary>
    /// 网格图。
    /// </summary>
    public abstract class GridGraph
    {
        /// <summary>
        /// 存放全部网格的二维数组。
        /// </summary>
        public readonly Grid[,] Grids;

        /// <summary>
        /// 可能会被查找的网格。
        /// </summary>
        protected readonly System.Collections.Generic.List<Grid> OpenList = new System.Collections.Generic.List<Grid>();

        /// <summary>
        /// 已经查找过的网格。
        /// </summary>
        protected readonly System.Collections.Generic.List<Grid> CloseList = new System.Collections.Generic.List<Grid>();

        /// <summary>
        /// 使用指定的行列数和网格序列初始化 <see cref="GridGraph"/> 类的新实例。
        /// </summary>
        /// <param name="rowCount">行数。</param>
        /// <param name="columnCount">列数。</param>
        /// <param name="grids">成员为网格的序列。</param>
        /// <exception cref="System.ArgumentOutOfRangeException"><paramref name="rowCount"/> 或 <paramref name="columnCount"/> 为 0 或为负。</exception>
        /// <exception cref="System.ArgumentNullException"><paramref name="grids"/> 为 <see langword="null"/> .</exception>
        public GridGraph(int rowCount, int columnCount, System.Collections.Generic.IEnumerable<Grid> grids)
        {
            if (rowCount < 1)
            {
                throw new System.ArgumentOutOfRangeException(nameof(rowCount));
            }

            if (columnCount < 1)
            {
                throw new System.ArgumentOutOfRangeException(nameof(columnCount));
            }

            if (grids == null)
            {
                throw new System.ArgumentNullException(nameof(grids));
            }

            Grids = new Grid[rowCount, columnCount];
            using (var enumerator = grids.GetEnumerator())
            {
                for (var i = 0; i < rowCount; i++)
                {
                    for (var j = 0; j < columnCount; j++)
                    {
                        if (enumerator.MoveNext())
                        {
                            var element = enumerator.Current;
                            if (element != null)
                            {
                                var grid = (Grid) element.Clone();
                                grid.RowIndex    = i;
                                grid.ColumnIndex = j;
                                grid.From        = default;
                                grid.G           = default;
                                Grids[i, j]      = grid;
                                continue;
                            }
                        }

                        Grids[i, j] = new Grid
                        {
                            RowIndex    = i,
                            ColumnIndex = j,
                            Walkable    = true,
                            From        = default,
                            G           = default
                        };
                    }
                }
            }
        }

        /// <summary>
        /// 尝试寻找路径。
        /// </summary>
        /// <param name="startNodeRowIndex">起点网格的行坐标。</param>
        /// <param name="startNodeColumnIndex">起点网格的列坐标。</param>
        /// <param name="endNodeRowIndex">终点网格的行坐标。</param>
        /// <param name="endNodeColumnIndex">终点网格的列坐标。</param>
        /// <param name="gridDistanceCalculator">网格距离计算器。</param>
        /// <param name="path">路径。</param>
        /// <returns>成功地找到路径了吗？</returns>
        public virtual bool TryFindPath(int startNodeRowIndex, int startNodeColumnIndex, int endNodeRowIndex, int endNodeColumnIndex, IGridDistanceCalculator gridDistanceCalculator, out System.Collections.Generic.List<Grid> path)
        {
            if (gridDistanceCalculator == null)
            {
                path = default;
                return false;
            }

            Grid startGrid;
            try
            {
                startGrid = Grids[startNodeRowIndex, startNodeColumnIndex];
            }
            catch (System.IndexOutOfRangeException)
            {
                path = default;
                return false;
            }
            if (!startGrid.Walkable)
            {
                path = default;
                return false;
            }

            Grid endGrid;
            try
            {
                endGrid = Grids[endNodeRowIndex, endNodeColumnIndex];
            }
            catch (System.IndexOutOfRangeException)
            {
                path = default;
                return false;
            }
            if (!endGrid.Walkable)
            {
                path = default;
                return false;
            }

            foreach (var element in Grids)
            {
                element.From = default;
                element.G    = default;
            }

            if (startGrid == endGrid)
            {
                path = new System.Collections.Generic.List<Grid> {startGrid};
                return true;
            }

            OpenList.Clear();
            OpenList.Add(startGrid);
            CloseList.Clear();

            while (OpenList.Count != 0)
            {
                var frontier = GetFrontier(gridDistanceCalculator, endGrid);
                OpenList.Remove(frontier);
                CloseList.Add(frontier);
                if (OnSearchNeighbors(frontier, endGrid))
                {
                    path = new System.Collections.Generic.List<Grid>();
                    var grid = endGrid;
                    while (grid != startGrid)
                    {
                        path.Add(grid);
                        grid = grid.From;
                    }
                    path.Add(startGrid);
                    path.Reverse();
                    return true;
                }
            }

            path = default;
            return false;
        }

        private Grid GetFrontier(IGridDistanceCalculator gridDistanceCalculator, Grid endGrid)
        {
            var frontier   = default(Grid);
            var minF       = default(double);
            var hasElement = false;

            foreach (var element in OpenList)
            {
                var f = element.G + gridDistanceCalculator.CalculatorDistance(element, endGrid);

                if (!hasElement)
                {
                    hasElement = true;
                    frontier   = element;
                    minF       = f;
                }
                else if (f <= minF)
                {
                    frontier = element;
                    minF     = f;
                }
            }

            return frontier;
        }

        /// <summary>
        /// 对当前预估代价最低的网格的未被查找过的邻居进行查找。
        /// </summary>
        /// <param name="frontier">当前预估代价最低的网格。</param>
        /// <param name="endGrid">终点网格。</param>
        /// <returns>当前预估代价最低的网格的未被查找过的邻居中包含有终点网格吗？</returns>
        protected abstract bool OnSearchNeighbors(Grid frontier, Grid endGrid);

        /// <summary>
        /// 获取网格在上、左、下、右方向的可通行的邻居。
        /// </summary>
        /// <param name="grid">网格。</param>
        /// <returns>返回网格在上、左、下、右方向的可通行的邻居。</returns>
        protected System.Collections.Generic.IEnumerable<Grid> GetPositiveWalkableNeighbors(Grid grid)
        {
            Grid neighbor = default;

            // 上
            try
            {
                neighbor = Grids[grid.RowIndex - 1, grid.ColumnIndex];
            }
            catch (System.IndexOutOfRangeException) { }
            if (neighbor != default && neighbor.Walkable)
            {
                yield return neighbor;
            }

            // 左
            try
            {
                neighbor = Grids[grid.RowIndex, grid.ColumnIndex - 1];
            }
            catch (System.IndexOutOfRangeException) { }
            if (neighbor != default && neighbor.Walkable)
            {
                yield return neighbor;
            }

            // 下
            try
            {
                neighbor = Grids[grid.RowIndex + 1, grid.ColumnIndex];
            }
            catch (System.IndexOutOfRangeException) { }
            if (neighbor != default && neighbor.Walkable)
            {
                yield return neighbor;
            }

            // 右
            try
            {
                neighbor = Grids[grid.RowIndex, grid.ColumnIndex + 1];
            }
            catch (System.IndexOutOfRangeException) { }
            if (neighbor != default && neighbor.Walkable)
            {
                yield return neighbor;
            }
        }

        /// <summary>
        /// 获取网格在右上、左上、左下、右下方向的可通行的邻居。
        /// </summary>
        /// <param name="grid">网格。</param>
        /// <returns>返回网格在右上、左上、左下、右下方向的可通行的邻居。</returns>
        protected System.Collections.Generic.IEnumerable<Grid> GetObliqueWalkableNeighbors(Grid grid)
        {
            Grid neighbor = default;

            // 右上
            try
            {
                neighbor = Grids[grid.RowIndex - 1, grid.ColumnIndex + 1];
            }
            catch (System.IndexOutOfRangeException) { }
            if (neighbor != default && neighbor.Walkable)
            {
                yield return neighbor;
            }

            // 左上
            try
            {
                neighbor = Grids[grid.RowIndex - 1, grid.ColumnIndex - 1];
            }
            catch (System.IndexOutOfRangeException) { }
            if (neighbor != default && neighbor.Walkable)
            {
                yield return neighbor;
            }

            // 左下
            try
            {
                neighbor = Grids[grid.RowIndex + 1, grid.ColumnIndex - 1];
            }
            catch (System.IndexOutOfRangeException) { }
            if (neighbor != default && neighbor.Walkable)
            {
                yield return neighbor;
            }

            // 右下
            try
            {
                neighbor = Grids[grid.RowIndex + 1, grid.ColumnIndex + 1];
            }
            catch (System.IndexOutOfRangeException) { }
            if (neighbor != default && neighbor.Walkable)
            {
                yield return neighbor;
            }
        }
    }
}
